package com.prp.keywords_search_statistic;

/**
 * 双向链表，没有头结点 有序（根据LinkedListNode的readCount排序）
 * 
 * @author zw
 * 
 */
public class LinkedList {

	private LinkedListNode head;
	private LinkedListNode tail;

	public LinkedList() {
		head = tail = null;
	}

	public LinkedListNode getFirst() {
		return head;
	}

	public LinkedListNode getLast() {
		return tail;
	}

	/**
	 * 添加到链表的开头
	 * 
	 * @param node
	 * @return
	 */
	public LinkedListNode addFirst(LinkedListNode node) {
		if (head == null) {
			node.previous = node.next = null;
			head = tail = node;
		} else {
			node.previous = null;
			node.next = head;
			head.previous = node;
			this.head = node;
		}
		return node;
	}

	public LinkedListNode addFirst(String key) {
		LinkedListNode node = new LinkedListNode(key, head, null, 0);
		return addFirst(node);
	}

	/**
	 * 添加到链表的最后
	 * 
	 * @param key
	 * @return
	 */
	public LinkedListNode addLast(String key) {
		LinkedListNode node = new LinkedListNode(key, null, tail, 0);
		return addLast(node);
	}

	public LinkedListNode addLast(LinkedListNode node) {
		if (tail == null) {
			node.next = node.previous = null;
			head = tail = node;
		} else {
			node.next = null;
			node.previous = tail;
			tail.next = node;
			this.tail = node;
		}
		return node;
	}

	/**
	 * 当关键字的搜索次数增加时对关键字的位置进行调整，保证列表是有序的。
	 * 
	 * @param node
	 * @return
	 */
	public LinkedListNode shiftUp(LinkedListNode node) {
		if (node == null) {
			return null;
		}
		if (node == this.head) {
			return node;
		}
		LinkedListNode prePointer = node.previous;
		while (prePointer != null) {
			if (prePointer.readCount < node.readCount) {
				prePointer = prePointer.previous;
			} else {
				break;
			}
		}
		
		if (prePointer == null) {
			remove(node);
			node = addFirst(node);
		} else {
			remove(node);
			node.next = prePointer.next;
			node.previous = prePointer;
			prePointer.next = node;
			if (node.next != null){
				node.next.previous = node;
			}
		}
		return node;
	}
	public void remove(LinkedListNode node){
		if(node == null){
			return ;
		}
		if(node.previous != null){
			node.previous.next = node.next;
		}else{
			head = node.next;
		}
		if( node.next != null){
			node.next.previous = node.previous;
		}else{
			tail = node.previous;
		}
	}

	/**
	 * 清空链表
	 */
	public void clear() {
		LinkedListNode node = getLast();
		while (node != null) {
			remove(node);
			node = node.previous;
		}
		head = tail = null;
	}

	/**
	 * 按顺序打印
	 */
	public String toString() {
		LinkedListNode node = head;
		StringBuilder buf = new StringBuilder();
		while (node != null) {
			buf.append(node.toString()).append(", ");
			node = node.next;
		}
		return buf.toString();
	}
}
